package com.wangzemin.leetcode.num29;

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor==0){
            throw new RuntimeException();
        }
        boolean dividendPositive = dividend>0;
        boolean divisorPositive = divisor>0;
        long shang = divideHelper(Math.abs((long)dividend),Math.abs((long)divisor));

        if (dividendPositive==divisorPositive){
            if (shang>Integer.MAX_VALUE)shang=Integer.MAX_VALUE;
            return (int)shang;
        }
        return (int)-shang;
    }

    public long divideHelper(long dividend, long divisor) {
        if (dividend<divisor){
            return 0;
        }
        if (dividend < divisor + divisor) {
            return 1;
        }
        long divisorPow2 = divisor;
        long power2 = 1;
        while (divisorPow2+divisorPow2< dividend) {
            divisorPow2 = divisorPow2 << 1;
            power2 = power2 + power2;
        }
        return power2 + divideHelper(dividend-divisorPow2,divisor);
    }

//    public static void main(String[] args){
//        Solution solution = new Solution();
//        System.out.println(solution.divide(-2147483648,-1));
//    }
}